\documentclass[paper=a4, fontsize=11pt]{scrartcl}
\newcommand{\bfvec}[1]{\mbox{\boldmath$#1$}}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{charter}
\usepackage[top=0.75in, bottom=1in, left=0.5in, right=0.5in]{geometry} 
\usepackage{amsmath,amssymb}
\title{	
\normalfont \normalsize 
\textsc{Shanghai Jiaotong University, Zhiyuan College} \\ [25pt]
\huge Homework 7 \\
}
\author{Feng Shi}
\date{\normalsize\today}
\begin{document}
\maketitle
\begin{enumerate}

\item[Ex 4.5]{\Large Solution:}
\begin{enumerate}
\item[1.]
Let 
$\bfvec{v_1}=
	\left( \begin{array}{c}
		x_{1}\\
		x_{2}\\
		\vdots \\
		x_{n} 
	\end{array} \right)
$, then $x_1^2+x_2^2+\cdots +x_n^2=1$, and
$
\bfvec{Av_1}=
	\left( \begin{array}{c}
			a_1(x_1+x_2+\cdots +x_\frac{n}{k}) \\
			a_1(x_1+x_2+\cdots +x_\frac{n}{k}) \\
			a_1(x_1+x_2+\cdots +x_\frac{n}{k}) \\
			a_2(x_{\frac{n}{k}+1}+x_{\frac{n}{k}+2}+\cdots +x_{\frac{2n}{k}})\\
			\vdots\\
			a_K(x_{\frac{(k-1)n}{k}+1}+\cdots +x_{n})
	\end{array} \right)
$.\\ \\
\begin{align*}
|\bfvec{Av_1}|&=\sqrt{\frac{n}{k}\bigg( a_1^2(\sum_{i=1}^{\frac{n}{k}}x_i)^2 
+a_2^2(\sum_{i=\frac{n}{k}+1}^{\frac{2n}{k}}x_i)^2
+\cdots 
+a_k(\sum_{i=\frac{(k-1)n}{k}+1}^{n}x_i)^2\bigg)}\\
&\leq \sqrt{\frac{n}{k}}\sqrt{a_1^2(\sum_{i=1}^{\frac{n}{k}}x_i^2)\frac{n}{k} 
+ a_2^2(\sum_{i=\frac{n}{k}+1}^{\frac{2n}{k}}x_i^2)\frac{n}{k}
+\cdots 
+a_k(\sum_{i=\frac{(k-1)n}{k}+1}^{n}x_i^2})\frac{n}{k} \tag{by Cauchy's inequality}\\
&\leq \frac{n}{k}\sqrt{a_1^2 \sum_{i=1}^{n}x_i^2 }\tag{$a_1>a_2>\cdots >a_k$}\\
&=\frac{na_1}{k}
\end{align*}
If and only if $x_1=x_2=\cdots=x_\frac{n}{k}=\sqrt{\frac{k}{n}}$ 
and $x_{\frac{n}{k}+1}=\cdots=x_n=0$, $|\bfvec{Av_1}|$ arrives at maxima. That is:
$\bfvec{v_1}^T=
	\left(\sqrt{\frac{k}{n}} \quad \sqrt{\frac{k}{n}}\quad \cdots\quad \sqrt{\frac{k}{n}}\right)
$.\\
Let 
$\bfvec{v_2}=
	\left( \begin{array}{c}
		y_{1}\\
		y_{2}\\
		\vdots \\
		y_{n} 
	\end{array} \right)
$,
then
$$y_1^2+y_2^2+\cdots+y_n^2=1$$
$$y_1+y_2+\cdots+y_\frac{n}{k}=0$$
So 
\begin{align*}
|\bfvec{Av_2}|&=\sqrt{a_2^2(\sum_{i=\frac{n}{k}+1}^{\frac{2n}{k}}y_i)^2
+a_3^2(\sum_{i=\frac{2n}{k}+1}^{\frac{3n}{k}}y_i)^2
+\cdots+a_k^2(\sum_{i=\frac{(k-1)n}{k}+1}^{n}y_i)^2}\\
&\leq \frac{n}{k}\sqrt{a_2^2\bigg(\sum_{i=\frac{n}{k}+1}^{n}y_i^2\bigg)}
\end{align*}
If and only if $y_{\frac{n}{k}+1}=y_{\frac{n}{k}+1}=\cdots=y_{\frac{2n}{k}}=\sqrt{\frac{k}{n}}$,
and $y_{\frac{2n}{k}+1}=\cdots=y_n=0$, \bfvec{Av_2} arrives at maxima.\\
Similarly, for \bfvec{v_i}, if and only if the $(i-1)\frac{n}{k}+1 \sim i\frac{n}{k}$'s component
of \bfvec{v_i} is $\sqrt{\frac{k}{n}}$ and other components $0$, 
\bfvec{Av_i} arrives at maxima.\\
\item[2.]
A set of singular vector is a set of $k$ vectors looks like:
$$\bordermatrix{ & 1 &\ldots &\frac{(i-1)n}{k}+1 &\cdots &\frac{in}{k} & n\cr
				1&0 &\ldots \cr
				\vdots& \vdots \cr
\frac{(i-1)n}{k}+1 &  &  &\sqrt{\frac{k}{n}} \cr
			\vdots &  &  &  &\ddots \cr 
\frac{in}{k}       &  &  &  &  &\sqrt{\frac{k}{n}} \cr
			\vdots \cr
				n& & & & & & &0
		}=\bfvec{v_i}$$
each \bfvec{v_i} corresponding to the $i$'th block in \bfvec{A}.\\
Other possible sets of singular vectors are all linear combinations of this set of
vectors.
\end{enumerate} % end of ex 4.5

\vspace{20pt}
\item[Ex 4.12]{\Large Solution:}

Let 
$\bfvec{v_1}=
	\left( \begin{array}{c}
		x\\y 
	\end{array} \right)
	$, and $x^2+y^2=1$. Then
	$$\bfvec{Av_1}=\left( \begin{array}{cc}
			 1 & 2\\ 3 &4$$
	\end{array} \right)
\left(\begin{array}{c} x\\y \end{array} \right)
=\left(\begin{array} {c} x+2y\\3x+4y \end{array}\right)
	$$
We maximize $|\bfvec{Av_1}|=\sqrt{(x+2y)^2+(3x+4y)^2}
=\sqrt{10x^2+28xy+20y^2}$.\\
Take 
\begin{align*}
	L(x,y,\lambda)=10x^2+28xy+20y^2+\lambda(x^2+y^2+1)
	\tag{use Lagrange multiplier to find local maxima} 
\end{align*}

\begin{displaymath}
\left\{ \begin{array}{ll}
\frac{\partial L}{\partial x}=20x+28y+2\lambda x&=0\\ \\
\frac{\partial L}{\partial y}=28x+40y+2\lambda y &=0\\ \\
\frac{\partial L}{\partial\lambda}=x^2+y^2-1 &=0
\end{array} \right.
\end{displaymath}
And solving these equations gives
\begin{displaymath}
\left\{ \begin{array}{l}
		x=\pm \sqrt{\frac{\sqrt{221}+5}{2\sqrt{221}}}\\
		y=\pm \sqrt{\frac{\sqrt{221}-5}{2\sqrt{221}}}
\end{array} \right.
\quad or \quad
\left\{ \begin{array}{l}
		x=\pm \sqrt{\frac{\sqrt{221}-5}{2\sqrt{221}}}\\
		y=\pm \sqrt{\frac{\sqrt{221}+5}{2\sqrt{221}}}
\end{array} \right.
\end{displaymath}
Take two orthonormal vectors (from the solution):
$$
\bfvec{v_1}=\left( \begin{array}{l}
\sqrt{\frac{\sqrt{221}-5}{2\sqrt{221}}}\\\\- \sqrt{\frac{\sqrt{221}+5}{2\sqrt{221}}}
\end{array}\right)
\quad and \quad
\bfvec{v_2}=\left( \begin{array}{l}
\sqrt{\frac{\sqrt{221}+5}{2\sqrt{221}}}\\\\\sqrt{\frac{\sqrt{221}-5}{2\sqrt{221}}}
\end{array}\right)
$$
And the singular values are:
$$
\sigma_1=\sqrt{15+\sqrt{221}} \quad \sigma_2=\sqrt{15-\sqrt{221}}
$$
And
$$
\bfvec{u_1}=\left( \begin{array}{l}
\sqrt{\frac{\sqrt{221}-10}{2\sqrt{221}}}\\\\\sqrt{\frac{\sqrt{221}+10}{2\sqrt{221}}}
\end{array}\right)
\quad and \quad
\bfvec{u_2}=\left( \begin{array}{l}
\sqrt{\frac{\sqrt{221}+10}{2\sqrt{221}}}\\\\-\sqrt{\frac{\sqrt{221}-10}{2\sqrt{221}}}
\end{array}\right)
$$
So
\begin{align*}
\bfvec{A}&=\bfvec{UDV}^T\\
&=\left(\begin{array}{ll}
\sqrt{\frac{\sqrt{221}-10}{2\sqrt{221}}}&\sqrt{\frac{\sqrt{221}+10}{2\sqrt{221}}}\\\\
\sqrt{\frac{\sqrt{221}+10}{2\sqrt{221}}}&-\sqrt{\frac{\sqrt{221}-10}{2\sqrt{221}}}
\end{array}\right)
\left(\begin{array}{lr}
\sqrt{15+\sqrt{221}} & 0\\\\
0 & \sqrt{15-\sqrt{221}}
\end{array}\right)
\left(\begin{array}{ll}
\sqrt{\frac{\sqrt{221}-5}{2\sqrt{221}}}&\sqrt{\frac{\sqrt{221}+5}{2\sqrt{221}}}\\\\
-\sqrt{\frac{\sqrt{221}+5}{2\sqrt{221}}}&\sqrt{\frac{\sqrt{221}-5}{2\sqrt{221}}}
\end{array}\right)
\end{align*}
\end{enumerate} % end of questions
\end{document}

